package com.zxy.leetcode._00000_00099._00030_00039;

/**
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 *
 * 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 标签：动态规划、字符串
 */
public class Test00032 {

    public static void main(String[] args) {
        Test00032 test = new Test00032();
        System.out.println(test.longestValidParentheses("(()"));
        System.out.println(test.longestValidParentheses(")()())"));
        System.out.println(test.longestValidParentheses("()(())"));
        System.out.println(test.longestValidParentheses("(()())"));
    }

    /*
    如果当前是“(”，前面没法满足有效括号
    如果当前是“)”，前一个要满足的条件
        可以是“(”
        还可以是“)”，但是再前面要是“((”
     */
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int max = 0;
        char[] chars = s.toCharArray();

        for (int i=1; i<chars.length; i++) {
            if (chars[i] == ')') {
                if (dp[i-1] > 0) {
                    int l = i - dp[i-1] - 1;
                    if (l >= 0 && chars[l] == '(') {
                        dp[i] = dp[i-1] + 2;

                        if (l-1>=0) {
                            dp[i] += dp[l-1];
                        }
                    }
                }else if (chars[i-1] == '(') {
                    if (i > 2) {
                        dp[i] = dp[i-2] + 2;
                    }else {
                        dp[i] = 2;
                    }
                }else if (chars[i-1] == ')') {
                    if (i > 2) {
                        int l = i - dp[i-2] - 3;
                        if (l >= 0 && chars[l] == '(' && chars[l+1] == '(') {
                            dp[i] = dp[i-2] + 4;

                            if (l-1>=0) {
                                dp[i] += dp[l-1];
                            }
                        }
                    }
                }
            }

            max = Math.max(max, dp[i]);
        }

        return max;
    }
}
